package com.lgc.algorithm.ErFenQuery;

//查找第一个相等的元素，也就是说等于查找key值的元素有好多个，返回这些元素最左边的元素下标。
public class Test2 {
    public static void main(String args[]) {
        int[] array = new int[]{0, 1, 2, 3, 4, 4, 6, 17, 18, 29};

        Test2 test = new Test2();
        int index1 = test.binarySerach(array, 4);
        int index = test.binarySerach2(array, 4);

        System.out.println(index);
    }

    int binarySerach(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if (array[mid] >= key) {
                right = mid-1;
            } else {
                left = mid + 1;
            }
        }

        if(left<array.length && array[left]==key){
            return left;
        }

        return -1;
    }

    int binarySerach2(int[] array, int key) {
        int left = 0;
        int right = array.length - 1;

        while (left <= right) {
            int mid = (left + right) / 2;

            if(left==right){
                if(array[left]==key){
                    return left;
                }
                else {
                    return -1;
                }
            }

            if (array[mid] >= key) {
                right = mid;
            } else {
                left = mid + 1;
            }
        }

        return -1;
    }
}
